A. Field of Invention
The present invention is directed toward the field of information systems. More particularly, the present invention is directed toward providing multi-dimensional organization, maintenance, and views of records.
B. Description of Related Art
Database management systems are employed to manage large amounts of records in a database. These systems provide for storing, accessing, and manipulating the records. Records may be extracted from a database management system by submitting a query to the system. In response to the query, the database management system searches the records in the database to identify and provide a set of records which correspond to the requirements set forth in the query.
Once a set of records is provided in response to the query, a person who submitted the query may wish to view the records in a particular format. It is often desirable to view the records in a multi-dimensional format. In a multi-dimensional format, each value in a record is categorized as being either a dimension value or a measure value. The dimension values characterize the measure values, and the measure values contain data to be either quantitatively or qualitatively analyzed.
For example, a company may have sold video cassette recorders, televisions, and stereos in 1995 and 1996 in both an eastern region and a western region of the United States. The measure of sales made by the company may be characterized by a number of different dimensions. One possible set of dimensions includes a region dimension, year dimension, and product dimension.
FIG. 1(a) illustrates a traditional multi-dimensional record structure 90 characterizing the company""s sales with respect to the region, year, and product dimensions. The record structure 90 is formed so that cells 911-12 in the structure 90 are filled with sales measure values, which are retrieved from a database or other source of records such as a data file. The x-axis 92 of the structure 90 is sectioned into regions that correspond to a set of product dimension values, namely, video cassette recorder (xe2x80x9cVCRxe2x80x9d), television (xe2x80x9cTVxe2x80x9d), and stereo. The y-axis 93 of the structure 90 is sectioned into regions that correspond to a set of region dimension values, namely East and West. The z-axis 94 of the structure 90 is sectioned into regions that correspond to a set of year dimension values, namely, 1995 and 1996.
Each sales measure value residing in a cell 911-12 is characterized by the combination of a product dimension value, a region dimension value, and a year dimension value. The measure value in the front upper left hand cell 91, is characterized by the VCR product dimension value, East region dimension value, and 1995 year dimension value. Accordingly, the measure value in cell 911 indicates the sales of VCR""s in the East region of the United States in 1995.
The multi-dimensional record structure 90 in FIG. 1(a) may also be represented in the format of the multi-dimensional record structure 100 shown in FIG. 1(b). Structure 100 provides a two dimensional set of cells 1011-12 containing sales measure values. Each axis of a cell in structure 100 is characterized by a set of dimension values. The horizontal axis 104 of the structure 100 is divided into a set of sections. Each of these sections corresponds to a unique pair of a year dimension value and a product dimension value. The vertical axis 103 of the structure 100 is also divided into a set of sections. Each of these sections corresponds to a unique region dimension value. The upper left hand cell 101, in the structure 100 contains a measure value indicating the sales of VCR""s in the East region of the United States in 1995.
FIG. 2 illustrates a conventional multi-dimensional record management system 110, which creates multi-dimensional record structures. The multi-dimensional record management system 110 retrieves records to be employed in a multi-dimensional record structure from a data source, such as a data file or database. Once the multi-dimensional record structure is created no further access to the data source is necessary. Alternatively, data may be directly input to the record management system 110 by a user.
The multi-dimensional record management system 110 includes an input control unit 112, display unit 121, several data storage modules, and several processing engines. These components are coupled together by a system bus 122 that provides for the transfer of data, address, and control signals between the components. The system bus 122 may be extended outside the multi-dimensional record management system 110 to couple the record management system 110 to a data source.
The input control unit 112 enables a record management system 110 user to provide instructions or data to the system 110 through an input device, such as a keyboard or mouse. The display unit 121 assists in providing a user interface and displays different views of constructed multi-dimensional record structures.
The data storage modules include a multi-dimensional record structure storage unit 119, a metadata storage unit 118, and a display memory 120. The metadata storage unit 118 contains sets of rules that are provided by the user of the record management system 110. For each dimension that is to be included in the multi-dimensional record structure, the metadata rules enumerate all of the dimension values that are associated with the dimension. The rules also specify any hierarchical relationship that exists between different dimensions and their respective dimension values. This specification of hierarchical relationships requires a user to identify all hierarchical relationships between each dimension value in a set of related dimensions. These rules are entered by the user prior to instructing the system 110 to build a multi-dimensional record structure, since the system 110 employs the rules in forming the record structure.
The task of entering such highly detailed rules into the metadata storage unit 118 places a significant burden on the user. The user must be knowledgeable of all dimension records that will be incorporated into the record structure. Typically, users are aware of the dimensions that are relevant to a measure being provided in the record structure. However, the set of dimension values that make up each dimension is not always readily apparent to the user.
For example, in the record structure shown in FIG. 1(a), the user must provide the metadata storage unit 118 with each associated dimension value for the product dimension, year dimension, and region dimension. This may not appear difficult in light of FIG. 1(a), but the magnitude of the user""s task is greatly increased if any dimension includes a great number of dimension values. This is a reality for many users, who wish to include a dimension in the record structure that may be comprised of hundreds or thousands of dimension values. A product dimension for a record structure being prepared to view sales measures in a large corporation could easily be made up of hundreds of product dimension values.
Further, the dimension values that are associated with a dimension can change over time. This prevents a standard metadata set of rules from being developed for continued use. For example, a set of product dimension values for a large company may change over time, as new products are introduced and old products are discontinued. The user of the record system 110 will have to know or learn all of the product dimension values that were in existence over the time period for which the product dimension is being represented in the record structure. In FIG. 1(a), this time period is only two years, but this time period could be extended to any number of years in many circumstances.
It is desirable to eliminate the need for the user of a multi-dimensional record management system to provide detailed listings of dimension values and relationships between particular dimension values. Such an elimination would decrease the time and effort required by the user to prepare a multi-dimensional view of a set of records.
The multi-dimensional record structure storage unit 119 stores the multi-dimensional record structure that is created by the system 110. The amount of memory required for storing such a structure can be very significant. In a traditionally formed structure, the number of measure cells is equal to the product of the number of dimension values associated with each of the dimensions. In FIG. 1(a), the number of measure cells is 12, which is calculated by multiplying the number of region dimension values (2), the number of year dimension values (2), and the number of product dimension values (3).
Forming such a structure is wasteful, if a dimension value associated with one dimension being represented on an axis does not coexist with another dimension value associated with another dimension being represented on the same axis. For example, in FIG. 1(a), stereo cell entries are provided for both 1995 and 1996 in both the East and West regions. If stereos were not an available product in 1995, then the record structure 90 contains two wasted memory locations (cells 913, 916). This is because the 1995 dimension value and stereo dimension value would not coexist in any record to characterize a sales measure value.
The East and West cell entries for stereo sales in 1995 (cells 913, 916) could therefore be eliminated, but there is no mechanism in a traditional record management system 110 to provide for such an elimination of cells. Although wasted memory due to the inclusion of two extraneous cells may not appear significant, the amount of wasted memory locations in the record structure can quickly multiply as the number of dimensions and dimension values increases.
The inclusion of unnecessary cell locations in the record structure also causes the time for constructing the record structure to be increased. For each unnecessary cell, the record management system 110 spends processing time determining that there is no measure value to be inserted into the cell. This extra time results in inconvenience and delay to the user, as well as unnecessary use of record management system resources. It would therefore be desirable to minimize the number of unnecessary cell locations in a multi-dimensional structure.
The display memory 120 is loaded with data representing different views of the record structure in the multi-dimensional record structure storage unit 119. The display unit 121 then displays the views that are stored in the display memory 120.
The processing engines include a query engine 114, record structure engine 115, display engine 116, and control engine 117. The control engine 117 provides for transferring information between the input control unit 112 and the rest of the system 110. The query engine 114 provides for performing a user specified query to retrieve data values and measure values from a data source.
The record structure engine 115 retrieves dimension values and measure values that are obtained from a data source in response to a query. The record structure engine 115 then maps the retrieved values into a multi-dimensional record structure in the multi-dimensional record structure storage unit 119. The record structure engine 115 constructs the multi-dimensional record structure based on inputs provided by the system""s user and the rules in the metadata storage unit 118.
In traditional record management systems, such as system 110, the record structure engine 115 has been limited to building the record structure based on the results of only a single query. Further, once the record structure is formed, any records from an additional subsequent query cannot be incorporated into the existing record structure. In order to incorporate the records from an additional query, an entirely new record structure must be formed from the records returned by a single query that retrieves both the original records and the additional records.
The inability to incorporate additional query records into an existing record structure requires system users to anticipate all the measures and dimensions that may be desired for viewing prior to building the record structure. This often causes system users to include more dimensions and measures than are actually needed in a record structure to insure that no possible combination of relevant dimensions and measures are left out. The unused dimensions and measures wastefully consume memory in the record management system 110. Further, as a result of viewing the information in the record structure, the system user often wishes to view the measure values with respect to additional unanticipated dimensions. In traditional systems, this requires the construction of an entirely new record structure, which includes the unanticipated dimensions. This is undesirable, since the time required for building a traditional record structure can be extensive.
It would be desirable for the record management system to integrate records from a new query with records from an original query to augment an existing record structure. Such an augmentation would avoid the need for constructing an entirely new record structure from the two queries. Such an ability to augment would also avoid the need for building a very big record structure initially, since new dimensions and measures could be added at a later time.
The display engine 116 provides for retrieving user specified views of the record structure in the multi-dimensional record structure storage unit 119 and placing them in the display memory 120. The display engine 120 then provides for the views to be displayed to the user on the display unit 121. The views are limited to being slices of the record structure along planes in the record structure that are perpendicular to a record structure axis.
As a result, the display engine 116 is limited in the number of views that may be provided from the records returned by the query. Further, dimensions that are hierarchically related may not be viewed on opposite axes. This is because the traditional record structure engine 115 integrates hierarchically related dimensions into a single axis in the record structure. As stated above, the hierarchical relationship between both different dimensions and the dimension values in each dimension are entered into the metadata storage unit 118 by the system""s user.
For example, the traditionally formed record structure 105 shown in FIG. 3 is the same as the record structure 90 shown in FIG. 1(a), except that record structure 105 includes a dimension for sales offices. The sales office dimension values include New York, Boston, San Francisco, and Seattle sales offices. The sales office dimension is hierarchically related to the region dimension, since it provides a more granular breakdown of each region dimension value. The user entered metadata will be required to include entries to reflect each of the following relationships: 1) the New York and Boston dimension values are hierarchically related to the East dimension value; and 2) the San Francisco and Seattle dimension values are hierarchically related to the West dimension value. Accordingly, the sales office dimension values are represented on the y-axis of the record structure 105 along with the region dimension values.
Due to the format of the record structure in FIG. 3, it is not possible to obtain a view 106 of the record structure as shown in FIG. 4. In FIG. 4, the measure cells are viewed so that they are characterized on a horizontal axis by the sales office dimension and on a vertical axis by the region dimension. This view is not possible, because the dimension on the horizontal axis is hierarchically related to the dimension on the vertical axis. No corresponding orthogonal slice of the traditionally formed record structure 105 in FIG. 3 can be made, because the region and sales office dimensions are on the same axis in the record structure 105.
It is desirable for the record management system""s user to have more flexibility in viewing the records returned by a query. Given greater flexibility, the user would be able to view measure values that are characterized on any axis by any dimension, regardless of the dimension""s hierarchical relation to any other dimension. As a result, a more flexible record management system would be able to generate the view 106 in FIG. 4.
Accordingly, it is desirable for a multi-dimensional record management system to provide for the display of records in a multi-dimensional format at higher speeds with reduced memory usage. It is also beneficial for the record management system to reduce the burden on the user of providing a metadata list of each dimension value associated with a dimension and the hierarchical relationship between each dimension value. Such a record management system may also provide for the augmentation of a multi-dimensional record view with records that are retrieved from a subsequent query. Finally, it is desirable for the record management system to provide for viewing measure records with respect to different dimensions, regardless of the hierarchical relationship between different dimensions.
A multi-dimensional record management system in accordance with the present invention generates a multi-dimensional view of records without constructing a multi-dimensional record structure. This provides for views to be created using less time and less memory than is required for the traditional generation of a multi-dimensional view.
In the absence of a traditional multi-dimensional record structure, multi-dimensional views may be generated in accordance with the present invention from records that are retrieved using multiple queries. As a result, the measures and dimensions provided in a view may be expanded by performing a new query to gather new measures or dimension values and augmenting existing information in the record management system. Such augmentation is not possible in a traditional record management system.
Further, a record management system in accordance with the present invention is able to generate views independent of hierarchical relationships between dimensions. The record management system also has no need to be instructed about any association between dimensions and dimension values. Accordingly, the user of the record management system is relieved of providing much information that is necessary to the operation of traditional multi-dimensional record management systems.
A record management system in accordance with the present invention provides for generating a multi-dimensional view for a number of different measures. A set of records that include measure values associated with the different measures is retrieved in response to a set of queries. A number of different dimension values are also represented throughout the set of records, and each one of the dimension values is associated with at least one of a number of different dimensions.
The record management system maintains the set of records in a master table. A record structure foundation is generated to reflect the contents of the master table. In one embodiment of the present invention, the record structure foundation includes a master table index and a query map. The query map includes a query map record for each query in the set of queries. A query map record identifies a query and the dimensions and measures called for by the query.
The master table index includes dimension index records. Each dimension index record identifies a dimension value from the master table, an associated dimension, and each record in the master table that contains the dimension value.
The record management system uses the master table index to generate a multi-dimensional layout mapping for the measures to be viewed. The layout mapping includes a set of cells that are arranged with respect to a set of axes. A set of dimensions is represented on each axis, and each axis includes a set of groups of records from the master table. Each cell corresponds to a group on each axis. Each group of records on an axis includes records that contain a dimension value from each dimension represented on the axis. Each group contains at least one record, because no groups are assigned for dimension values that do not coexist in any record.
Once a layout mapping is generated, the record management system converts the layout mapping into a multi-dimensional view. For each cell in the layout mapping, measure results are determined based on the measure values in the records in each group corresponding to the cell. The measure results are loaded into the cells, and the multi-dimensional view is displayed.
A record management system in accordance with the present invention may include data storage units for implementing the master table, query map, master table index, and layout mapping. In order to perform the operations that are carried out in generating a multi-dimensional view, the record management system may also include a control engine, query engine, index engine, and layout engine. These processing engines and data storage units may be coupled together by a system bus to provide for the transfer of data between different components in the record management system.
The operations performed by the processing engines may be stored in the form of program code instructions in data storage mediums within the record management system, such as memory and mass storage devices. Alternatively, such program code instructions may be maintained on a portable storage medium and loaded into the record management system.